#ifndef BIGINT_HPP
#define BIGINT_HPP
#include <iostream>
#include <vector>
namespace myh {
    class BigInt {
    private:
        bool sign;
        std::vector<int> digits;
    public:
        static constexpr int BASE=100000000;
        static constexpr int BASE_DIGITS=8;
    public:
        BigInt() : sign(true), digits{0} {}
        BigInt(long long);
        BigInt(const std::string&);
        BigInt(const BigInt& other) = default;
        BigInt& operator=(const BigInt& other) = default;
        BigInt operator-() const;
        BigInt operator+(const BigInt&) const;
        BigInt operator-(const BigInt&) const;
        BigInt operator*(const BigInt&) const;
        BigInt operator/(const BigInt&) const;
        BigInt operator%(const BigInt&) const;
        BigInt& operator+=(const BigInt& other) { *this = *this + other; return *this; }
        BigInt& operator-=(const BigInt& other) { *this = *this - other; return *this; }
        BigInt& operator*=(const BigInt& other) { *this = *this * other; return *this; }
        BigInt& operator/=(const BigInt& other) { *this = *this / other; return *this; }
        BigInt& operator%=(const BigInt& other) { *this = *this % other; return *this; }
        BigInt& operator++() { *this += 1; return *this; }
        BigInt operator++(int) { BigInt tmp = *this; ++*this; return tmp; }
        BigInt& operator--() { *this -= 1; return *this; }
        BigInt operator--(int) { BigInt tmp = *this; --*this; return tmp; }
        bool operator==(const BigInt& other) const {
            return sign == other.sign && digits == other.digits;
        }
        bool operator!=(const BigInt& other) const { return !(*this == other); }
        bool operator<(const BigInt&) const;
        bool operator>(const BigInt& other) const { return other < *this; }
        bool operator<=(const BigInt& other) const { return !(*this > other); }
        bool operator>=(const BigInt& other) const { return !(other > *this); }
        BigInt operator<<(size_t) const;
        BigInt operator>>(size_t) const;
        BigInt abs() const {
            BigInt result = *this;
            result.sign = true;
            return result;
        }
        BigInt withSign(bool newSign) const {
            BigInt result = *this;
            if(result != BigInt(0)) result.sign=newSign;
            return result;
        }
        bool isOdd() const {
            if (digits.empty()) return false;
            return (digits[0] & 1) != 0;
        }
        BigInt pow(const BigInt&) const;
        friend std::ostream& operator<<(std::ostream&,const BigInt&);
        friend std::istream& operator>>(std::istream&,BigInt&);
        BigInt powCore(const BigInt&) const;
    };
    template<std::integral T>
    T gcd(T a,T b){
        int tmp;
        while(b!=0){
            tmp=a%b;
            a=b;
            b=tmp;
        }
        return a;
    }
    template<std::integral T>
    T lcm(T a,T b){
        return a/gcd(a,b)*b;
    }
    BigInt gcd(BigInt a,BigInt b){
        BigInt tmp=a;
        while(b!=0){
            tmp=b;
            b=a%b;
            a=tmp;
        }
        return a;
    }
    BigInt lcm(BigInt a,BigInt b){
        return a/gcd(a,b)*b;
    }
}
#endif